/*
 * @lc app=leetcode id=63 lang=cpp
 *
 * [63] Unique Paths II
 */
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        if (m < 1) {
            return 0;
        }
        int n = obstacleGrid[0].size();
        if (m <= 1 || n <= 1) {
            return check(obstacleGrid) ? 0 : 1;
        }
        
        vector<vector<int>>& grid = obstacleGrid;
        vector<vector<unsigned>> memo(m, vector<unsigned>(n));
        memo[0][0] = 1 - grid[0][0];
        for (int i=1; i<m; i++) {
            if (grid[i][0] == 1 || memo[i-1][0] == 0) {
                memo[i][0] = 0;
            } else {
                memo[i][0] = 1;
            }
        }
        for (int i=1; i<n; i++) {
            if (grid[0][i] == 1 || memo[0][i-1] == 0) {
                memo[0][i] = 0;
            } else {
                memo[0][i] = 1;
            }
        }

        for (int i=1; i<m; i++) {
            for (int j=1; j<n; j++) {
                if (grid[i][j] == 1) {
                    memo[i][j] = 0;
                } else {
                    memo[i][j] = memo[i-1][j] + memo[i][j-1];
                }
            }
        }
        return memo[m-1][n-1];
    }

    int check(vector<vector<int>>& obstacleGrid) {
        int cnt = 0;
        for (auto v : obstacleGrid) {
            for (auto i : v) {
                if (i == 1) {
                    cnt ++;
                }
            }
        }
        return cnt;
    }
};

